package com.lfg.leetcode.leetcode0;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class No22GenerateParenthesis {

    private static String data = "()";


    public static List<String> generateParenthesis(int n) {
        List<String> ret = new ArrayList<String>();

        generateParenthesis(ret, "", n, n);
        return ret;
    }

    public static void generateParenthesis(List<String> ret, String content, int left, int right) {
        if (left < 0 || right < 0 || left > right) {
            return;
        }
        if (left <= 0 && right <= 0) {
            ret.add(content);
            return;
        }
        if (left > 0) {
            generateParenthesis(ret, content + "(", left - 1, right);
        }
        if (right > left) {
            generateParenthesis(ret, content + ")", left, right - 1);
        }
    }

    public static List<String> generateParenthesis2(int n) {
        List<String> ret = new ArrayList<String>();
        for (int i = 0; i < n; i++) {
            if (ret.size() == 0) {
                ret.add(data);
                continue;
            }
            Set<String> tmp = new HashSet<String>();
            for (String s : ret) {
                for (int j = 0; j < s.length(); j++) {
                    StringBuilder sb = new StringBuilder(s);
                    tmp.add(sb.insert(j, data).toString());
                }
            }
            ret = new ArrayList<>(tmp);
        }
        return ret;
    }

    public static void main(String[] args) {
        System.out.println(generateParenthesis(3));
//        System.out.println(threeSum(new int[]{-2,0,0,2,2}));
    }
}
